/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : sunzb
 * @date: 2019/5/16
 */
public class _31_120_Triangle {

    public static int minimumTotal1(List<List<Integer>> triangle) {
        int lvls = triangle.size();
        int[] min = new int[lvls];
        List<Integer> lastLvl = triangle.get(lvls - 1);
        for (int i = 0; i < lastLvl.size(); i++)
            min[i] = lastLvl.get(i);
        for (int lvl = lvls - 2; lvl >= 0; lvl--) {
            List<Integer> list = triangle.get(lvl);
            for (int i = 0; i < list.size(); i++)
                min[i] = Math.min(min[i], min[i + 1]) + list.get(i);
        }
        return min[0];
    }

    public static int minimumTotal(List<List<Integer>> triangle) {
        // 状态 dp[level, index] 路径和的最小值
        // 转移方程 dp[level, index] = min(dp[level + 1, index], dp[level + 1, index + 1]) + dp[level, index]
        int lvls = triangle.size();
        List<Integer> listLevel1 = triangle.get(lvls - 1);
        int[][] dp = new int[lvls][listLevel1.size()];
        for (int i = 0; i < listLevel1.size(); i++)
            dp[lvls - 1][i] = listLevel1.get(i);
        for (int lvl = lvls - 2; lvl >= 0; lvl--) {
            List<Integer> list = triangle.get(lvl);
            for (int i = 0; i < list.size(); i++)
                dp[lvl][i] = Math.min(dp[lvl + 1][i], dp[lvl + 1][i + 1]) + list.get(i);
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        //[[2],[3,4],[6,5,7],[4,1,8,3]]
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(new ArrayList(Arrays.asList(2)));
        triangle.add(new ArrayList(Arrays.asList(3, 4)));
        triangle.add(new ArrayList(Arrays.asList(6, 5, 7)));
        triangle.add(new ArrayList(Arrays.asList(4, 1, 8, 3)));
        System.out.println(minimumTotal(triangle));
        System.out.println(minimumTotal1(triangle));
    }
}
